#include "item.h"
#include "search.h"

void st_init(int maxN) 
{ 
  st = (info*)malloc(maxN*sizeof(info));
  N = 0; 
};

int st_count() 
{ 
  return N; 
};

void st_insert(info a)
{ 
  int j = N++; 
  int v = key(a);
  while (j>0 && less(v, key(st[j-1]))) {  
    st[j] = st[j-1]; 
    j--; 
  }
  st[j] = a;
};

info st_search(int v)
{ 
  int j;
  for (j = 0; j < N; j++) {
    if (eq(v, key(st[j]))) 
      return st[j];
    if (less(v, key(st[j]))) 
      break;
  }
  return nullItem;
};

info bsearch(int l, int r, int v)
{ 
  int m = (l+r)/2;
  if (l > r) 
    return nullItem;
  if eq(v, key(st[m])) 
	 return st[m];
  if (l == r) 
    return nullItem;
  if less(v, key(st[m])) 
	   return bsearch(l, m-1, v);
  else 
    return bsearch(m+1, r, v);
};
